//给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 示例1： 
//
// 
//
// 
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
// 
//
// 示例2： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
// 
//
// 示例3： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 100] 
// 0 <= node.val <= 9 
// 输入数据保证链表代表的数字无前导 0 
// 
//
// 
//
// 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。 
//
// 
//
// 注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/ 
// Related Topics 栈 链表 数学 👍 58 👎 0


package leetcode.editor.cn;

import com.leetcode.utils.ListNode;

//Java：链表中的两数相加
public class LMSNwu {
    public static void main(String[] args) {
        Solution solution = new LMSNwu().new Solution();
        // TO TEST
        ListNode l1 = new ListNode(new int[]{2,4,9});
        ListNode l2 = new ListNode(new int[]{5,6,4,9});
        System.out.println(solution.addTwoNumbers(l1, l2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 两个链表是逆序的 两个数都不会以0开头
            int jinwei = 0;
            ListNode listNode = new ListNode();
            ListNode tail = listNode;
            int il1, il2, sum;
            while (l1 != null && l2 != null) {
                il1 = l1.val;
                il2 = l2.val;
                sum = il1 + il2 + jinwei;
                if (sum >= 10) {
                    tail.val = sum - 10;
                    jinwei = 1;
                } else {
                    tail.val = sum;
                    jinwei = 0;
                }
                l1 = l1.next;
                l2 = l2.next;
                if (l1 != null || l2 != null) {
                    tail.next = new ListNode();
                    tail = tail.next;
                }
            }

            while (l1 != null) {
                il1 = l1.val;
                sum = il1 + jinwei;
                if (sum >= 10) {
                    tail.val = sum - 10;
                    jinwei = 1;
                } else {
                    tail.val = sum;
                    jinwei = 0;
                }
                l1 = l1.next;
                if (l1 != null) {
                    tail.next = new ListNode();
                    tail = tail.next;
                }
            }
            while (l2 != null) {
                il2 = l2.val;
                sum = il2 + jinwei;
                if (sum >= 10) {
                    tail.val = sum - 10;
                    jinwei = 1;
                } else {
                    tail.val = sum;
                    jinwei = 0;
                }
                l2 = l2.next;
                if (l2 != null) {
                    tail.next = new ListNode();
                    tail = tail.next;
                }
            }
            if (jinwei > 0) {
                tail.next = new ListNode();
                tail = tail.next;
                tail.val = jinwei;
            }
            if (tail.val != -1) {
                // 去除listNode最后一个节点
            }
            return listNode;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
